package kyssion.leetcode.num51_100;

import kyssion.leetcode.util.ListNode;

public class code86_分割列表 {
    public static void main(String[] args) {
        ListNode listNode = ListNode.createListNode(
                new int[]{

                }
        );
        listNode = new code86_分割列表().partition(listNode, 2);
        ListNode.showListNode(listNode);
    }

    public ListNode partition(ListNode head, int x) {
        ListNode big = new ListNode(-1);
        ListNode small = new ListNode(-1);
        ListNode b = big;
        ListNode s = small;
        while (head != null) {
            if (head.val >= x) {
                b.next = head;
                head = head.next;
                b = b.next;
                b.next = null;
            } else {
                s.next = head;
                head = head.next;
                s = s.next;
                s.next = null;
            }
        }
        if (big.next != null) {
            s.next = big.next;
        }
        return small.next;
    }

    public ListNode partition2(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        // 1、创建连个临时节点，将小于x的放入less中，大于等于x放入more
        ListNode lessNode = new ListNode(0);
        ListNode moreNode = new ListNode(0);
        ListNode less = lessNode;
        ListNode more = moreNode;

        while (head != null) {
            if (head.val < x) {
                less.next = head;
                less = less.next;
            } else {
                more.next = head;
                more = more.next;
            }
            head = head.next;
        }
        // 2、拼接less和more
        more.next = null;
        less.next = moreNode.next;
        return lessNode.next;
    }
}
